package com.kevinkk.hashmap;

import java.util.*;

/**
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 */

public class ThreeSum {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);   // 必须首先排序，否则无法使用双指针
            for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1])        // 对 i 进行去重
                    continue;
                int l = i + 1, r = nums.length - 1, target = -nums[i];
                while (l < r) {
                    int sum = nums[l] + nums[r];
                    if (sum == target) {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[l]);
                        temp.add(nums[r]);
                        while (l < r && nums[l] == nums[l + 1]) // 对 l 进行去重
                            l++;
                        while (l < r && nums[r] == nums[r - 1]) // 对 r 进行去重
                            r--;
                        // 在退出循环后，左右指针还必须移动一次，才能保证指向了新的元素
                        l++;
                        r--;
                        res.add(temp);
                    } else if (sum > target) {
                        r--;
                    } else {
                        l++;
                    }
                }
            }
            return res;
        }
    }
}
